//
// Created by francklinson on 2021/6/20.
//
#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <functional>

using namespace std;

/**
 * 家庭成员类
 */
class FamilyPerson {

public:
    string name; // 姓名
    vector<FamilyPerson *> sons; // 后代
    bool isAlive; // 存活状态

    explicit FamilyPerson(string personName) : name(std::move(personName)) {
        isAlive = true;
    }

};

class ThroneInheritance {
private:
    FamilyPerson *familyRoot; // 国王 根节点
    unordered_map<string, FamilyPerson *> family; // 姓名和指针的映射
public:
    /**
     * 构造函数
     * @param kingName
     */
    explicit ThroneInheritance(const string& kingName) {
        familyRoot = new FamilyPerson(kingName);
        family[kingName] = familyRoot;
    }

    /**
     * 某个家族成员添加儿子
     * @param parentName
     * @param childName
     */
    void birth(const string& parentName, const string& childName) {
        auto parentPtr = family[parentName];
        auto newPerson = new FamilyPerson(childName);
        parentPtr->sons.push_back(newPerson);
        family[childName] = newPerson;

    }

    /**
     * 成员死亡
     * @param name
     */
    void death(const string& name) {
        family[name]->isAlive = false;
    }

    /**
     * 获得继承顺序结果
     * @return
     */
    vector<string> getInheritanceOrder() {
        vector<string> ans;
        preOrderSearch(familyRoot, ans);
        return ans;
    }

    /**
     * 前序遍历多子树
     * @param root
     */
    void preOrderSearch(FamilyPerson *root, vector<string> &ans) {
        if (root->isAlive)
            ans.push_back(root->name);
        for (auto &x:root->sons) {
            preOrderSearch(x, ans);
        }
    }
};

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance* obj = new ThroneInheritance(kingName);
 * obj->birth(parentName,childName);
 * obj->death(name);
 * vector<string> param_3 = obj->getInheritanceOrder();
 */

class ThroneInheritance2 {
private:
    unordered_map<string, vector<string>> edges;
    unordered_set<string> dead;
    string king;

public:
    ThroneInheritance2(string kingName) : king{move(kingName)} {}

    void birth(string parentName, string childName) {
        edges[move(parentName)].push_back(move(childName));
    }

    void death(string name) {
        dead.insert(move(name));
    }

    vector<string> getInheritanceOrder() {
        vector<string> ans;

        function<void(const string &)> preorder = [&](const string &name) {
            if (!dead.count(name)) {
                ans.push_back(name);
            }
            if (edges.count(name)) {
                for (const string &childName: edges[name]) { // 遍历子代
                    preorder(childName);
                }
            }
        };

        preorder(king);
        return ans;
    }
};

int main() {
    auto t = new ThroneInheritance("king"); // 继承顺序：king
    t->birth("king", "andy"); // 继承顺序：king > andy
    t->birth("king", "bob"); // 继承顺序：king > andy > bob
    t->birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
    t->birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
    t->birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
    t->birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
    t->getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
    t->death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
    auto ans = t->getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]
    for (auto &x:ans) cout << x << endl;
    delete t;
    return 0;
}